25635번: 자유 이용권 i번째 놀이기구 이용권의 횟수가 A[i]로 주어진다 모든 놀이기구를 이용하고 싶은데 연속으로 같은 놀이기구를 사용하지 않는다 최대 몇번 사용가능한가? A = [1,1,3]이면 3번, 2번, 3번, 1번, 3번으로 5번 가능하다 처음에 생각하기에는 무조건 큰 값끼리 모아서 쌍으로 이용하면 된다고 생각을 했는데 A = [1,2,3,4,5]라고 한다면 5번 이용가능한거랑 4번 이용가능한거 모아서 5 4 5 4 5 4 5 4 이렇게 하면 8번 쓰는거고 5가 1번 남고 [1,2,3,0,1]에서 3,5 해서 3번이 2번 남고 [1,2,2,0,0]에서 3번 2번 가져와서 3,2,3,2 해서 [1,0,0,0,0] 해서 1번을 쓰면 된다는 식으로 n = int(input())A = list..
1. 재배열 부등식(rearrangement inequality) 실수 $x_{1} 1,2,..,n의 임의의 순열 $\sigma_{1}, \sigma_{2}, ... , \sigma_{n}$으로부터 $$x_{1}y_{n} + x_{2}y_{n-1} + ... + x_{n}y_{1} 2. 증명 $S1 = x_{1}y_{1} + x_{2}y_{2} + .... + x_{a}y_{a} + .... + x_{b}y_{b} + ... + x_{n}y_{n}$에서 $y_{a} $S2 = x_{1}y_{1} + x_{2}y_{2} + ... + x_{a}y_{b} + ... + x_{b}y_{a} + ... + x_{n}y_{n}$ 둘을 뺴면 $S1 - S2 = x_{a}(y_{a} - y_{b}) + x_{..
13904번: 과제 (acmicpc.net) 과제의 기간 제한이 있고 해당 과제를 수행했을 때 얻는 가치가 서로 다르다 하루에 하나씩 과제만 처리할 수 있다. 주어진 과제들을 적절히 처리해서 최대 가치를 구한다면? --------------------------------------------------------------------------------------------------------------------------- 처음에는 과제 점수가 높은 순서대로 내림차순 정렬해서 현재 날짜랑 비교해서 처리할 수 있는 과제면 일단 가져가고 날짜랑 비교했을 때 처리할 수 없는 과제면.. 지금까지 가져간 과제들 비교해서... 실제 처리할 수 있는지 체크해보는것? 4 604 401 202 503 304 1..
19177번: Klothes (acmicpc.net) 1부터 n까지의 자연수 중에서 각각 1번씩만 사용하고, 정확히 k개의 정수만 사용해서 합을 s로 만드는 방법을 찾는 문제 n이 40000까지이고 테스트케이스가 8000개이다 보니 단순한 방법보다는 O(N)정도에 하나는 해결해야 만약 s가 가능한 범위를 벗어난다면 일단 만들수가 없다. s의 최솟값은 1부터 k까지 합 s의 최댓값은 n-k+1,n-k+2,...,n까지의 합 만약 s가 (1부터 k까지 합) 반대로 이 범위 안이라면 확실하게 만들 수 있다는 것이 보장된다. (1부터 k까지의 합) = a (n-k+1,...,n까지의 합) = b라고 할 때, a,a+1,a+2,..,b-1,b까지의 모든 정수는 반드시 만들 수 있다. 어떤 정수는 안되는게 있..
1. 문제 코딩테스트 연습 - n + 1 카드게임 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 무작위로 뒤섞인 1부터 n까지 카드가 n장 있고, coin개의 동전을 가지고 있는데 처음에 n/3장을 가지고 시작 각 라운드가 시작할때 카드를 2장 뽑는데 카드 1장당 동전 1개를 소모해서 가지거나 버릴 수 있다 가지고 있는 카드에 적힌 수의 합이 n+1이 되도록 카드 2장을 내고 다음 라운드로 넘어간다. 카드를 내지 못하거나 모든 카드를 뽑아 더 이상 뽑을 수 없으면 게임 종료 게임을 가장 ..
1. 문제 11497번: 통나무 건너뛰기 (acmicpc.net) 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 2. 풀이 요약하자면 인접한 원소간 차이의 최댓값이 최소가 되도록 배열을 정렬할때, 그 최솟값을 구하는 문제 단순히 크기 순으로 정렬한다고 하더라도.. [a1,a2,a3,...,an]에서 인접한 원소간 차이의 최댓값은 an-a1이므로, 배열의 최댓값과 최솟값의 차이이므로 이것이 최소일리는 없다 만약 크기순으로 정렬한다면, a1 < a2 < a3 < ... < an일때, 이들이 인접했을때, 원소간 ..
